package leetcode.其他;

/**
 * @author: levi
 * @description: https://leetcode.cn/problems/climbing-stairs/
 * @date: 2022-9-13 13:36
 * @version: 1.0
 */
public class 爬楼梯_70 {
    public static void main(String[] args) {
        System.out.println(climbStairs(5));
        System.out.println(climbStairs2(5));
    }

    // 递归
    public static int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        // 就是我第一次走1个，和第一次走两个的计算个数之和，因为我只能走两种
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    // 非递归，循环迭代
    public static int climbStairs2(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        int result = 0;
        int prePre = 1;
        int pre = 2;
        for (int i = 3; i <= n; i++) {
            result = pre + prePre;
            prePre = pre;
            pre = result;
        }
        return result;
    }
}
